package com.ai.zuochengyun.phase01.class03;

import java.util.Stack;

/**
 * 回文结构
 */
public class Code09_Palindrome {
    private static class Node {

        int value;
        Node next;
        public Node(int value) {
            this.value = value;
        }
        public Node next(Node next) {
            this.next = next;
            return this;
        }
    }

    public static boolean isPalindrome1(Node head) {
        if (head == null) {
            return true;
        }
        // 压入栈
        Stack<Node> stack = new Stack<>();
        Node cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }

        // 逐一弹出，和原来的链表进行比对
        cur = head;
        while (cur != null) {
            if (cur.value != stack.pop().value) {
                return false;
            }
            cur = cur.next;
        }
        return true;
    }

    public static boolean isPalindrome2(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return false;
        }

        // 奇数找到中点位置，偶数找到上中点位置
        Node fast = head;
        Node slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // 将中点位置到尾节点位置的链表进行反转
        Node tail = slow;
        Node n1 = tail.next;
        Node n2 = null;
        while (n1 != null) {
            n2 = n1.next;
            n1.next = tail;
            tail = n1;
            n1 = n2;
        }

        // 分别得到反转之后的头尾节点，head和n1
        Node h = head, t = tail;
        boolean flag = true;
        while (h != null && t != null) {
            if (h.value != t.value) {
                flag = false;
                break;
            }
            h = h.next;
            t = t.next;
        }

        // 还原链表
        // 尾节点
        Node temp = null;
        while (tail != null) {
            n1 = tail.next;
            tail.next = temp;
            temp = tail;
            tail = n1;
        }
        return flag;
    }

}
